Simplex-Algorithmus (vereinfacht):
Input: Matrix $A \in \IR^{k \times n}$, Vektoren $b \in \IR^k$, $c \in \IR^n$, Basis $B \subseteq [n]$ zu Ecke v. $P^=(A,b)$
Output: Optimale Lösung von $\min c^Tx \text{ u.d.N. } x \in P^=(A,b)$

---

1. Setze $N = [n] \setminus B$ .....................// Nichtbasis
2. While $r_N^T := c_B^T(A^B)^{-1}A^N-c_N^T \not\leq 0$ Do
3. .. Wähle den ersten Index $s$ mit $(r_N)_{s} > 0$
4. .. Wähle den ersten Index $p$ mit \[\frac{((A^B)^{-1}b)_{p}}{((A^B)^{-1}A^N)_{p,s}} = \min_{i \in [k]}\Set{\frac{((A^B)^{-1}b)_{i}}{((A^B)^{-1}A^N)_{i,s}} | ((A^B)^{-1}A^N)_{i,s} > 0}\] .. // Falls kein solcher Index existiert, ist das Problem unbeschränkt
5. .. Vertausche $N[s]$ und $B[p]$ ...........// Gehe zu neuer Ecke über
6. Bestimme die durch $B$ beschriebene Ecke $x \in P^=(A,b)$
7. Return $x$